// https://www.lintcode.com/problem/word-squares/description

// class Solution {
// public:
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
     */
     
// Input
// ["abat","baba","atan","atal"]
// Output
// []
// Expected
// [["baba","abat","baba","atal"],["baba","abat","baba","atan"]] 可以重复的？
     
    // void getPermutaion(vector<string> words, vector<string> perm, vector<vector<string>>& result, vector<bool> visited) {
    //     if (!perm.empty() && perm.size() == perm[0].size())
    //     {
    //         result.push_back(perm);
    //     }
    //     for (int i = 0; i < words.size(); ++i)
    //     {
    //         if (visited[i]) continue;
    //         visited[i] = true;
    //         perm.push_back(words[i]);
    //         getPermutaion(words, perm, result, visited);
    //         perm.pop_back();
    //         visited[i] = false;
    //     }
    // }
    // bool check(vector<string> words)
    // {
    //     if (words.size() != words[0].size()) return false;
    //     for (int i = 0; i < words.size(); ++i)
    //     {
    //         // for (int j = 0; j < words[0].size(); ++j)
    //         for (int j = i; j < words[i].size(); ++j)
    //         {
    //             if (words[j][i] != words[i][j])
    //             {
    //                 return false;
    //             }
    //         }
    //     }
    //     return true;
    // }
    // vector<vector<string>> wordSquares(vector<string> &words) {
    //     vector<vector<string>> result;
    //     vector<string> perm;
    //     vector<vector<string>> tmp;
    //     vector<bool> visited(words.size(), false);
    //     getPermutaion(words, perm, tmp, visited);
        
    //     for (vector<string> per: tmp)
    //     {
    //         // for (string p: per)
    //         // {
    //         //     cout << p << endl;
    //         // }
    //         if (check(per)) result.push_back(per);
    //     }
    //     return result;
    // }
    
// };


// 他是从右边判断的，判断方块的右和底是否一样
class Solution {
public:
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
    */     
    vector<vector<string> > result;
    map<string, vector<string> >prefix;
    vector<string> storage; 
    int num;
    vector<vector<string> > wordSquares(vector<string> &words) {
        if(words.size() == 0) {
            return result;
        }
       for (auto w: words)
       {
           string tmp = "";
           prefix[tmp].push_back(w);
           for (auto s: w)
           {
               tmp += s;
               prefix[tmp].push_back(w);
           }
       }
       num = words[0].size();
       dfs(0);
       return result;
    }

    // 剪枝，后面有一列构成的前缀没有那就false
    bool check(int cur, string str) {
        for (int i = cur + 1; i < num; ++i)
        {
            string tmp = "";
            // for (int j = 0; j < num; ++j)
            for (int j = 0; j < cur; ++j)
            {
                tmp += storage[j][i];
            }
            tmp += str[i];
            if (prefix[tmp].size() == 0) return false;
        }
        return true;
    }

    void dfs(int cur) {
        if (cur == num)
        {
            result.push_back(storage);
            return;
        }
        string pre = "";
        for (auto s: storage)
        {
            pre += s[cur];
        }
        for (auto p: prefix[pre])
        {
            if (!check(cur, p)) continue;
            storage.push_back(p);
            dfs(cur + 1);
            storage.pop_back();
        }
    }
};